package top.hkyzf.study.leetcode.string;

import org.junit.Test;

import java.util.*;

/**
 * @author zhufeng
 * @version 1.0
 * @date 2022-2-21 10:18
 */
public class 推多米诺_838 {
    public String pushDominoes1(String dominoes) {
        char[] domin = dominoes.toCharArray();
        Queue<int[]> queue = new ArrayDeque<>();
        int[] mark = new int[dominoes.length()];
        int time = 1;
        for (int i = 0; i < dominoes.length(); i++) {
            if (domin[i] == 'L' || domin[i] == 'R') {
                // 位置索引、受力、时间
                queue.offer(new int[]{i, domin[i] == 'L' ? -1 : 1, time});
                mark[i] = time;
            }
        }
        while (!queue.isEmpty()) {
            int[] ints = queue.poll();
            int newI = ints[0] + ints[1];
            time = ints[2];
            if (newI < 0 || newI > domin.length-1) {
                continue;
            }
            if (mark[newI] == 0) {
                domin[newI] = ints[1] == -1 ? 'L' : 'R';
                queue.offer(new int[]{newI, ints[1], time+1});
                mark[newI] = time+1;
            } else {
                if (mark[newI]-1 == ints[2]) {
                    domin[newI] = '.';
                }
            }
        }
        return String.valueOf(domin);
    }

    public String pushDominoes(String dominoes) {
        char[] domain = dominoes.toCharArray();
        int length = domain.length;
        int[] mark = new int[length];
        Deque<int[]> deque = new ArrayDeque<>();
        for (int i = 0; i < length; i++) {
            if (domain[i] == '.') continue;
            int dire = domain[i] == 'L' ? -1 : 1;
            deque.add(new int[]{i, dire, 1});
            mark[i] = 1;
        }
        while (!deque.isEmpty()) {
            int[] info = deque.pollFirst();
            int loc = info[0], dire = info[1], time = info[2];
            int ne = loc + dire;
            if (domain[loc] == '.' || (ne < 0 || ne >= length)) continue;
            if (mark[ne] == 0) { // 首次受力
                deque.addLast(new int[]{ne, dire, time + 1});
                mark[ne] = time + 1;
                domain[ne] = dire == -1 ? 'L' : 'R';
            } else if (mark[ne] == time + 1) { // 多次受力
                domain[ne] = '.';
            }
        }
        return String.valueOf(domain);
    }

    @Test
    public void testPushDominoes () {
        String dominies = ".L.R...LR..L..";
        System.out.println(pushDominoes1(dominies));
    }
}
